/**
 * 300. longest increasing subsequence 最长递增子序列
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 */
class LongestIncreasingSubsequence {

    /**
     * 方法： 使用动态规划求解最长递增子序列问题
     *       dp[i]表示以nums[i]结尾的最长递增子序列长度
     *       对于每个位置i，枚举前面的位置j
     *       如果nums[i]>nums[j]，则可以将nums[i]接在以nums[j]结尾的子序列后面
     *
     * Args:
     *      nums: int[] - 输入的整数数组
     *
     * Returns:
     *      int: 最长递增子序列的长度
     *
     * Time: O(n^2) - 需要两层循环遍历数组
     *
     * Space: O(n) - 需要一个长度为n的数组存储动态规划状态
     */
    public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for(int i = 1; i < nums.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] +1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
    
    /**
     * 方法： 使用贪心+二分查找求解最长递增子序列问题
     *       维护一个tails数组，tails[i]表示长度为i+1的递增子序列的最小结尾值
     *       对于每个数字，二分查找它在tails中的插入位置
     *       如果插入位置等于当前最大长度，则最大长度加1
     *
     * Args:
     *      nums: int[] - 输入的整数数组
     *
     * Returns:
     *      int: 最长递增子序列的长度
     *
     * Time: O(nlogn) - 遍历数组O(n)，每次二分查找O(logn)
     *
     * Space: O(n) - 需要一个长度为n的数组存储tails
     */
    public int lengthOfLIS1(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums){
            int i = 0, j = res;
            while(i < j){
                int m = (i + j) / 2;
                if(tails[m] < num){
                    i = m + 1;
                }else{
                    j = m;
                }
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }
}